package Offer;

import java.util.HashMap;
import java.util.Map;

public class Offer39 {
    public int majorityElement(int[] nums) {
        int length = nums.length/2+1;
        Map<Integer,Integer> map = new HashMap();
        for(int i = 0 ; i < nums.length ; i++){
            if(map.containsKey(nums[i])){
                map.replace(nums[i],map.get(nums[i])+1);
                if(map.get(nums[i])>=length)
                    return nums[i];
            }
            else{
                map.put(nums[i],1);
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Offer39 offer39 = new Offer39();
        System.out.println(offer39.majorityElement(new int[]{1,2,3,2,2,5,2,9,2}));
    }
}
